package leetcodehot100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * JZ28对称的二叉树
 */
public class _101对称二叉树 {
    public boolean isSymmetric(TreeNode root) {
        return isTrue(root,root);
    }
    boolean isTrue(TreeNode root1,TreeNode root2){
        if(root1==null && root2==null)
            return true;
        if(root1==null || root2==null || root2.val!= root1.val)
            return false;
        return isTrue(root1.left,root2.right) && isTrue(root1.right,root2.left);
    }

    //层次遍历
    public boolean isSymmetrical2(TreeNode pRoot) {
        if(pRoot == null)
            return true;
        Queue<TreeNode> q1 = new LinkedList();
        Queue<TreeNode> q2 = new LinkedList();
        q1.offer(pRoot.left);
        q2.offer(pRoot.right);
        while (!q1.isEmpty() && !q2.isEmpty()){
            TreeNode left = q1.poll();
            TreeNode right = q2.poll();

            if(left==null && right == null)
                continue;
            if(left==null || right==null || left.val!=right.val)
                return false;

            q1.offer(left.left);
            q1.offer(left.right);

            q2.offer(right.right);
            q2.offer(right.left);
        }
        return true;
    }
}
